#include <iostream>
using namespace std;

int main() {
	int count = 0;
	cout << "input number for sorted:" ;
	cin >> count;

	int* arr = new int[count];

	for(int i=0; i<count; i++) {
		cin >> arr[i];
	}

	cout << "the array for sort:" << endl;

	for(int i=0; i<count; i++) {
		cout << arr[i] << " ";
	}

	//insert sort!
	for(int j=1; j<count; j++) {
		int key = arr[j];
		int i = j-1;
		while(i>=0 && arr[i]>key) {
			arr[i+1] = arr[i];
			i--;
		}
		arr[i+1] = key;
	}

	cout << endl << "sorted:" << endl;

	for(int i=0; i<count; i++) {
		cout << arr[i] << " ";
	}

	delete arr;

	return 0;
}
